class SLNode {
    constructor(k, level) {
        this.key = k;
        this.forwards = [];
        for (let i = 0; i < level; ++i) {
            this.forwards.push(new SLNodeLevel());
        }
        this.backward = null;
    }
};

class SLNodeLevel {
    constructor() {
        this.forward = null;
        this.span = 0;
    }
};

class SkipList {
    constructor(compFunc) {
        this.level = 0;
        this.head = null;
        this.tail = null;

        this.count = 0;
        this.maxLevel = 32;

        this.compFunc = compFunc || function () { return true };

        this.eleEqual = function (lhs, rhs) {
            if (!this.compFunc(lhs, rhs) && !this.compFunc(rhs, lhs))
                return true;
            return false;
        }
        this.createList();
    }
};

SkipList.prototype.getRandomLevel = function () {
    let level = 1;

    while (3 == Math.floor(Math.random() * 4))
        ++level;
    return this.maxLevel > level ? level : this.maxLevel;
}

SkipList.prototype.createList = function () {
    this.head = new SLNode(0, this.maxLevel);
    this.count = 0;
    this.level = 1;
}

SkipList.prototype.search = function (key) {
    let node = this.head;
    let rank = 0;
    for (let i = this.level - 1; i >= 0; --i) {
        while (node.forwards[i].forward && this.compFunc(node.forwards[i].forward.key, key)) {
            rank += node.forwards[i].span;
            node = node.forwards[i].forward;
        }
    }
    ++rank;
    node = node.forwards[0].forward;
    if (!node)
        return 0;
    if (this.eleEqual(node.key, key)) {
        return rank;
    } else {
        return 0;
    }
}

SkipList.prototype.insert = function (key) {
    let node = this.head;
    let rank = new Array(this.maxLevel);
    let update = new Array(this.maxLevel);

    for (let i = this.level - 1; i >= 0; --i) {
        rank[i] = i == (this.level - 1) ? 0 : rank[i + 1];
        while (node.forwards[i].forward && this.compFunc(node.forwards[i].forward.key, key)) {
            rank[i] += node.forwards[i].span;
            node = node.forwards[i].forward;
        }
        update[i] = node;
    }

    node = node.forwards[0].forward;
    if (node && this.eleEqual(node.key, key))
        return;

    let nodeLevel = this.getRandomLevel();
    if (nodeLevel > this.level) {
        for (let i = this.level; i < nodeLevel; ++i) {
            rank[i] = 0;
            update[i] = this.head;
            this.head.forwards[i].span = this.count;
        }
        this.level = nodeLevel;
    }

    let newNode = new SLNode(key, nodeLevel);

    for (let i = 0; i < nodeLevel; ++i) {
        node = update[i];
        let forward = node.forwards[i];
        let newForward = newNode.forwards[i];
        newForward.forward = forward.forward;
        newForward.span = forward.span - (rank[0] - rank[i]);
        forward.forward = newNode;
        forward.span = rank[0] - rank[i] + 1;
    }
    for (let i = nodeLevel; i < this.level; ++i) {
        update[i].forwards[i].span++;
    }

    newNode.backward = (update[0] == this.head) ? null : update[0];
    if (newNode.forwards[0].forward) {
        newNode.forwards[0].forward.backward = newNode;
    } else {
        this.tail = newNode;
    }
    ++this.count;
}

SkipList.prototype.remove = function (key) {
    let update = new Array(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; --i) {
        while (node.forwards[i].forward && this.compFunc(node.forwards[i].forward.key, key)) {
            node = node.forwards[i].forward;
        }
        update[i] = node;
    }
    node = node.forwards[0].forward;
    if (!node || !this.eleEqual(key, node.key))
        return;
    for (let i = 0; i < this.level; ++i) {
        let levelNode = update[i].forwards[i];
        let forward = levelNode.forward;
        if (forward != node) {
            --levelNode.span;
        } else {
            let nLevelNode = node.forwards[i];
            levelNode.forward = nLevelNode.forward;
            levelNode.span += nLevelNode.span - 1;
        }
    }
    if (node.forwards[0].forward) {
        node.forwards[0].forward.backward = node.backward;
    } else {
        this.tail = node.backward;
    }
    while (this.level > 1 && !this.head.forwards[this.level - 1].forward) {
        --this.level;
    }
    --this.count;
}

SkipList.prototype.dumpAllNodes = function () {

    for (let i = this.level - 1; i >= 0; --i) {
        let so = i + '----- ';
        process.stdout.write(so);
        let node = this.head;
        while (node.forwards[i].forward) {
            let o = node.key + '(' + node.forwards[i].span + ') ';
            process.stdout.write(o);
            node = node.forwards[i].forward;
        }
        let o = node.key + '(' + node.forwards[i].span + ') ';
        process.stdout.write(o);
        console.log();
    }
}

let sl = new SkipList((lhs, rhs) => {
    return lhs < rhs;
});
for (let i = 1; i < 20; ++i) {
    sl.insert(i);
}
//sl.dumpAllNodes();
// console.log(sl.search(10));
sl.remove(1);
sl.remove(19);
sl.remove(10);
sl.dumpAllNodes();
console.log(sl.search(18));
process.exit();